๐Ÿ‘ฉโ€๐Ÿ’ป 1012. ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

@Seongukbaek Posted December 28, 2021 ยท Updated December 28, 2021 ยท 6 min read

๋ฌธ์ œ

์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ”๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„ ๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  ์žˆ์œผ๋ฉด ์ด ์ง€๋ ์ด๋Š” ์ธ์ ‘ํ•œ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด, ๊ทธ ๋ฐฐ์ถ”๋“ค ์—ญ์‹œ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ์šฐ ๋„ค ๋ฐฉํ–ฅ์— ๋‹ค๋ฅธ ๋ฐฐ์ถ”๊ฐ€ ์œ„์น˜ํ•œ ๊ฒฝ์šฐ์— ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

ํ•œ๋‚˜๊ฐ€ ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋Š” ๋•…์€ ๊ณ ๋ฅด์ง€ ๋ชปํ•ด์„œ ๋ฐฐ์ถ”๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์‹ฌ์–ด ๋†“์•˜๋‹ค. ๋ฐฐ์ถ”๋“ค์ด ๋ชจ์—ฌ์žˆ๋Š” ๊ณณ์—๋Š” ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋งŒ ์žˆ์œผ๋ฉด ๋˜๋ฏ€๋กœ ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๋ฐฐ์ถ”๋“ค์ด ๋ช‡ ๊ตฐ๋ฐ์— ํผ์ ธ์žˆ๋Š”์ง€ ์กฐ์‚ฌํ•˜๋ฉด ์ด ๋ช‡ ๋งˆ๋ฆฌ์˜ ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•œ์ง€ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฐ์ถ”๋ฐญ์ด ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉด ์ตœ์†Œ 5๋งˆ๋ฆฌ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค. 0์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ์ง€ ์•Š์€ ๋•…์ด๊ณ , 1์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ๋•…์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1

์ž…๋ ฅ

  • ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ ๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ์ฒซ์งธ ์ค„์—๋Š” ๋ฐฐ์ถ”๋ฅผ ์‹ฌ์€ ๋ฐฐ์ถ”๋ฐญ์˜ ๊ฐ€๋กœ๊ธธ์ด M(1 โ‰ค M โ‰ค 50)๊ณผ ์„ธ๋กœ๊ธธ์ด N(1 โ‰ค N โ‰ค 50), ๊ทธ๋ฆฌ๊ณ  ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ์œ„์น˜์˜ ๊ฐœ์ˆ˜ K(1 โ‰ค K โ‰ค 2500)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ K์ค„์—๋Š” ๋ฐฐ์ถ”์˜ ์œ„์น˜ X(0 โ‰ค X โ‰ค M-1), Y(0 โ‰ค Y โ‰ค N-1)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘ ๋ฐฐ์ถ”์˜ ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์ถœ๋ ฅ

  • ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด ๋งˆ๋ฆฌ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Pair { private int first; private int second; Pair(int x, int y) { this.first = x; this.second = y; } public int getF() { return first; } public int getS() { return second; } }
  • Pair ์˜ ๊ตฌํ˜„์„ ์œ„ํ•ด ์œ„์™€ ๊ฐ™์€ class ๋ฅผ ์ƒ์„ฑํ–ˆ๋‹ค.
for (int a = 0; a < worm.size(); a++) { int vF = worm.get(a).getF(); int vS = worm.get(a).getS(); if (visited[vF][vS] == 0) { Queue<Pair> q = new LinkedList<>(); q.offer(worm.get(a)); visited[vF][vS] = 1; while (!q.isEmpty()) { Pair cur = q.poll(); for (int i = 0; i < 4; i++) { int nx = cur.getF() + x_ary[i], ny = cur.getS() + y_ary[i]; if (nx >= 0 && ny >= 0 && nx < M && ny < N) { if (visited[nx][ny] == 0 && map[nx][ny] == 1) { visited[nx][ny] = 1; q.offer(new Pair(nx, ny)); } } } } worms++; } }
  • ๋ฐฐ์ถ”์˜ ์œ„์น˜ ๋ฐ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์‚ฌ์šฉํ•ด ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฐ์ถ”์˜ ์œ„์น˜๋ฅผ Queue ์— DFS ๋ฐฉ์‹์œผ๋กœ ์ถ”๊ฐ€ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] x_ary = {0, 0, -1, 1}; int[] y_ary = {-1, 1, 0, 0}; int[][] map = null; int[][] visited = null; visited = new int[50][50]; while (T > 0) { int M = sc.nextInt(); int N = sc.nextInt(); int K = sc.nextInt(); int worms = 0; map = new int[M][N]; ArrayList<Pair> worm = new ArrayList<>(); for (int[] tmp : visited) Arrays.fill(tmp, 0); for (int i = 0; i < K; i++) { int x = sc.nextInt(); int y = sc.nextInt(); map[x][y] = 1; worm.add(new Pair(x, y)); } for (int a = 0; a < worm.size(); a++) { int vF = worm.get(a).getF(); int vS = worm.get(a).getS(); if (visited[vF][vS] == 0) { Queue<Pair> q = new LinkedList<>(); q.offer(worm.get(a)); visited[vF][vS] = 1; while (!q.isEmpty()) { Pair cur = q.poll(); for (int i = 0; i < 4; i++) { int nx = cur.getF() + x_ary[i], ny = cur.getS() + y_ary[i]; if (nx >= 0 && ny >= 0 && nx < M && ny < N) { if (visited[nx][ny] == 0 && map[nx][ny] == 1) { visited[nx][ny] = 1; q.offer(new Pair(nx, ny)); } } } } worms++; } } System.out.println(worms); T -= 1; } sc.close(); } } class Pair { private int first; private int second; Pair(int x, int y) { this.first = x; this.second = y; } public int getF() { return first; } public int getS() { return second; } }

โœ๏ธ Review

  • c++ ๋กœ ํ’€์—ˆ๋˜ ๋ฌธ์ œ๋ฅผ java ๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ๋‹ค์‹œ ํ’€์–ด๋ณธ ๋ฌธ์ œ
  • ๋…ผ๋ฆฌ ์ž์ฒด๋Š” ๊ธฐ๋ณธ์ ์ธ DFS๋ฅผ ์‚ฌ์šฉํ•œ ๋ฌธ์ œ์—ฌ์„œ java ๋ฌธ๋ฒ•์„ ์˜ค๋žœ๋งŒ์— ๋‹ค์‹œ ์จ๋ณธ ๋ฌธ์ œ์˜€๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

https://www.acmicpc.net/problem/1012

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€